package com.ztom.top100;

import java.util.HashMap;
import java.util.Map;

/**
 * LRU 缓存
 * <p>
 * https://leetcode-cn.com/problems/lru-cache/
 *
 * @author ZhangTao
 */
public class Code52LRUCache {

    class Node {
        public int k, v;
        public Node pre;
        public Node next;

        public Node(int k, int v) {
            this.k = k;
            this.v = v;
        }
    }

    class LRUCache {

        private Node head;
        private Node tail;
        private Map<Integer, Node> cache;
        private int capacity;
        private int size;

        public LRUCache(int capacity) {
            // 辅助节点
            this.head = new Node(-1, -1);
            this.tail = new Node(-1, -1);
            head.next = tail;
            tail.pre = head;
            this.cache = new HashMap<>(capacity);
            this.capacity = capacity;
            this.size = 0;
        }

        public int get(int key) {
            if (cache.containsKey(key)) {
                // 在缓存中, 找出并删除, 放到链表头部, 返回
                Node node = cache.get(key);
                deleteNode(node);
                insertHead(node);
                return node.v;
            }
            return -1;
        }

        public void put(int key, int value) {
            if (cache.containsKey(key)) {
                // 在缓存中, 找出并删除, 放到链表头部
                Node node = cache.get(key);
                deleteNode(node);
            } else {
                // 不在缓存中, 且容量已满, 删除尾节点, 放到链表头部
                if (size >= capacity) {
                    deleteTail();
                }
            }
            insertHead(new Node(key, value));
        }

        private void insertHead(Node node) {
            Node second = head.next;
            if (second == tail) {
                // 如果是空链表
                node.next = tail;
                tail.pre = node;
            } else {
                node.next = second;
                second.pre = node;
            }
            head.next = node;
            node.pre = head;

            cache.put(node.k, node);
            size++;
        }

        private void deleteNode(Node node) {
            if (node.next == tail) {
                // 如果是尾节点
                deleteTail();
                return;
            }

            node.pre.next = node.next;
            node.next.pre = node.pre;

            cache.remove(node.k);
            size--;
        }

        private void deleteTail() {
            Node del = tail.pre;
            del.pre.next = tail;
            tail.pre = del.pre;

            cache.remove(del.k);
            size--;

            del.pre = null;
            del.next = null;
            del = null;
        }
    }
}
